Several techniques for analysis and transformations are used in compilers.Among them, the peeling of loops for hoisting quasi-invariants can be used tooptimize generated code, or simply ease developers' lives. In this paper, weintroduce a new concept of dependency analysis borrowed from the field ofImplicit Computational Complexity (ICC), allowing to work with composedstatements called Chunks to detect more quasi-invariants. Based on anoptimization idea given on a WHILE language, we provide a transformation method- reusing ICC concepts and techniques - to compilers. This new analysiscomputes an invariance degree for each statement or chunks of statements bybuilding a new kind of dependency graph, finds the maximum or worst dependencygraph for loops, and recognizes if an entire block is Quasi-Invariant or not.This block could be an inner loop, and in that case the computationalcomplexity of the overall program can be decreased. We already implemented aproof of concept on a toy C parser 1 analysing and transforming the ASTrepresentation. In this paper, we introduce the theory around this concept andpresent a prototype analysis pass implemented on LLVM. In a very near future,we will implement the corresponding transformation and provide benchmarkscomparisons.
展开▼
